#define _CRT_SECURE_NO_WARNINGS 1 


#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include<assert.h>
#define MAX_VERTICES 10
#define INF 9999

// 景点结构体，用来存储景点相关信息
typedef struct {
    char name[50];
    int ticket_price;  // 新增景点门票价格成员变量（单位：元）
} Place;

// 边结构体，用来存储边的信息（两个景点以及距离、不同交通工具下的时间、费用等）
typedef struct Edge {
    int src, dest;
    int distance;
    // 假设三种交通工具：公交、地铁、打车，分别对应时间和费用
    int time_bus, cost_bus;
    int time_subway, cost_subway;
    int time_taxi, cost_taxi;
} Edge;

// 图结构体，包含景点数组和边数组
typedef struct Graph {
    Place places[MAX_VERTICES];
    Edge edges[MAX_VERTICES * (MAX_VERTICES - 1) / 2];
    int num_places;
    int num_edges;
} Graph;

// 初始化图
void initGraph(Graph* graph) {
    graph->num_places = 0;
    graph->num_edges = 0;
}

// 添加景点
void addPlace(Graph* graph, const char* name, int ticket_price) {
    strcpy(graph->places[graph->num_places].name, name);
    graph->places[graph->num_places].ticket_price = ticket_price;
    graph->num_places++;
}

// 添加边（两个景点之间的连接信息）
void addEdge(Graph* graph, int src, int dest, int distance,
    int time_bus, int cost_bus,
    int time_subway, int cost_subway,
    int time_taxi, int cost_taxi) {
    Edge edge = { src, dest, distance, time_bus, cost_bus, time_subway, cost_subway, time_taxi, cost_taxi };
    graph->edges[graph->num_edges++] = edge;
}

// 从文件中读取景点图（这里简单示意文件读取格式，假设文件按特定格式保存了景点和边的信息）
void readGraphFromFile(Graph* graph, const char* filename) {
    FILE* fp = fopen("graph.txt", "r");
    if (fp == NULL) {
        assert("文件打开失败\n"); 
        return; 
    }
    // 读取景点数量
    fscanf(fp, "%d", &graph->num_places);
    for (int i = 0; i < graph->num_places; i++) {
        char name[50];
        int ticket_price;
        fscanf(fp, "%s %d", name, &ticket_price);
        addPlace(graph, name, ticket_price);
    }
    // 读取边数量
    fscanf(fp, "%d", &graph->num_edges);
    for (int i = 0; i < graph->num_edges; i++) {
        fscanf(fp, "%d %d %d %d %d %d %d %d %d",
            &graph->edges[i].src, &graph->edges[i].dest, &graph->edges[i].distance,
            &graph->edges[i].time_bus, &graph->edges[i].cost_bus,
            &graph->edges[i].time_subway, &graph->edges[i].cost_subway,
            &graph->edges[i].time_taxi, &graph->edges[i].cost_taxi);
    }
    fclose(fp);
}

// 保存旅游路线到文件（这里简单将路线的景点序号输出到文件，你可以按需完善格式）
void saveRouteToFile(int route[], int num_visited, const char* filename) {
    FILE* fp = fopen("route.txt", "r");
    if (fp == NULL) {
        perror(" Error opening file");
        return;
    }
    for (int i = 0; i < num_visited; i++) {
        fprintf(fp, "%d ", route[i]);
    }
    fclose(fp);
}

// 寻找两个景点之间的最短路径（这里简单以距离为衡量标准，使用Floyd算法示例，你可以结合时间、费用等综合优化）
void floydWarshall(Graph graph, int dist[MAX_VERTICES][MAX_VERTICES]) {
    for (int i = 0; i < graph.num_places; i++) {
        for (int j = 0; j < graph.num_places; j++) {
            dist[i][j] = INF;
        }
        dist[i][i] = 0;
    }

    for (int i = 0; i < graph.num_edges; i++) {
        int src = graph.edges[i].src;
        int dest = graph.edges[i].dest;
        int distance = graph.edges[i].distance;
        dist[src][dest] = distance;
    }

    for (int k = 0; k < graph.num_places; k++) {
        for (int i = 0; i < graph.num_places; i++) {
            for (int j = 0; j < graph.num_places; j++) {
                if (dist[i][k] + dist[k][j] < dist[i][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j];
                }
            }
        }
    }
}

// 寻找经过所有景点的最佳旅游路线（这里简单使用贪心算法思路示例，可能不是最优解，可进一步优化）
void findBestRoute(Graph graph, int start, int route[MAX_VERTICES], int* num_visited, int* total_time, int* total_cost) {
    int visited[MAX_VERTICES] = { 0 };
    visited[start] = 1;
    *num_visited = 1;
    route[0] = start;
    *total_time = 0;
    *total_cost = graph.places[start].ticket_price;  // 算上起点景点门票费用

    int current = start;
    while (*num_visited < graph.num_places) {
        int min_distance = INF;
        int next_place = -1;
        for (int i = 0; i < graph.num_edges; i++) {
            if (graph.edges[i].src == current && !visited[graph.edges[i].dest]) {
                if (graph.edges[i].distance < min_distance) {
                    min_distance = graph.edges[i].distance;
                    next_place = graph.edges[i].dest;
                }
            }
        }
        if (next_place == -1) {
            break;
        }

        // 根据距离选择一种相对最优的交通工具（这里简单示例，可优化判断逻辑）
        int selected_transport = -1;
        int selected_time = INF;
        int selected_cost = INF;
        if (graph.edges[next_place].time_bus < selected_time && graph.edges[next_place].cost_bus < selected_cost) {
            selected_transport = 0;  // 0代表公交
            selected_time = graph.edges[next_place].time_bus;
            selected_cost = graph.edges[next_place].cost_bus;
        }
        if (graph.edges[next_place].time_subway < selected_time && graph.edges[next_place].cost_subway < selected_cost) {
            selected_transport = 1;  // 1代表地铁
            selected_time = graph.edges[next_place].time_subway;
            selected_cost = graph.edges[next_place].cost_subway;
        }
        if (graph.edges[next_place].time_taxi < selected_time && graph.edges[next_place].cost_taxi < selected_cost) {
            selected_transport = 2;  // 2代表打车
            selected_time = graph.edges[next_place].time_taxi;
            selected_cost = graph.edges[next_place].cost_taxi;
        }

        // 更新总时间、总费用
        *total_time += selected_time;
        *total_cost += graph.places[next_place].ticket_price + selected_cost;

        visited[next_place] = 1;
        route[(*num_visited)++] = next_place;
        current = next_place;
    }
}

int main() {
    Graph graph;
    initGraph(&graph);

    // 添加北京的十个景点以及对应的门票价格（示例价格，可按实际调整）
    addPlace(&graph, "故宫", 60);
    addPlace(&graph, "天安门", 0);
    addPlace(&graph, "八达岭长城", 40);
    addPlace(&graph, "颐和园", 30);
    addPlace(&graph, "鸟巢", 0);
    addPlace(&graph, "圆明园", 10);
    addPlace(&graph, "北海公园", 10);
    addPlace(&graph, "天坛", 15);
    addPlace(&graph, "景山公园", 2);
    addPlace(&graph, "南锣鼓巷", 0);

    // 假设添加一些边以及对应的距离、不同交通工具时间和费用信息（示例，需按实际调整）
    addEdge(&graph, 0, 1, 2, 10, 2, 8, 3, 5, 10);  // 故宫到天安门，距离2公里，公交10分钟2元，地铁8分钟3元，打车5分钟10元
    addEdge(&graph, 0, 2, 80, 120, 20, 90, 15, 60, 200);  // 故宫到八达岭长城，距离80公里，公交120分钟20元，地铁90分钟15元，打车60分钟200元
    addEdge(&graph, 0, 3, 30, 60, 5, 40, 6, 30, 50);  // 故宫到八达岭长城
    addEdge(&graph, 0, 3, 30, 60, 5, 40, 6, 30, 50);// 故宫到颐和园
    addEdge(&graph, 0, 4, 15, 30, 3, 20, 4, 15, 20);// 故宫到鸟巢
    addEdge(&graph, 0, 5, 20, 40, 4, 30, 5, 25, 30);// 故宫到圆明园
    addEdge(&graph, 0, 6, 10, 20, 3, 15, 4, 12, 20);// 故宫到北海公园
    addEdge(&graph, 0, 7, 12, 25, 3, 20, 4, 18, 25);// 故宫到天坛
    addEdge(&graph, 0, 8, 8, 16, 2, 12, 3, 10, 15);// 故宫到景山公园
    addEdge(&graph, 0, 9, 10, 20, 3, 15, 4, 12, 20); // 故宫到南锣鼓巷
    addEdge(&graph, 1, 2, 85, 130, 22, 95, 18, 70, 220); // 天安门到八达岭长城
    addEdge(&graph, 1, 3, 28, 56, 5, 38, 6, 28, 45); // 天安门到颐和园
    addEdge(&graph, 1, 4, 18, 36, 4, 24, 5, 18, 25);  // 天安门到鸟巢
    addEdge(&graph, 1, 5, 22, 44, 4, 32, 5, 26, 35);  // 天安门到圆明园
    addEdge(&graph, 1, 6, 12, 24, 3, 18, 4, 14, 22);  // 天安门到北海公园
    addEdge(&graph, 1, 7, 15, 30, 4, 22, 5, 20, 30);  // 天安门到天坛
    addEdge(&graph, 1, 8, 10, 20, 3, 15, 4, 12, 20);  // 天安门到景山公园
    addEdge(&graph, 1, 9, 12, 24, 3, 18, 4, 14, 22); // 天安门到南锣鼓巷
    addEdge(&graph, 2, 3, 60, 90, 10, 70, 12, 50, 150);    // 八达岭长城到颐和园
    addEdge(&graph, 2, 4, 90, 135, 18, 100, 20, 80, 250);  // 八达岭长城到鸟巢
    addEdge(&graph, 2, 5, 85, 128, 16, 95, 18, 75, 230); // 八达岭长城到圆明园
    addEdge(&graph, 2, 6, 75, 113, 15, 85, 16, 65, 200); // 八达岭长城到北海公园
    addEdge(&graph, 2, 7, 80, 120, 16, 90, 18, 70, 220);// 八达岭长城到天坛
    addEdge(&graph, 2, 8, 78, 117, 15, 88, 16, 68, 210);   // 八达岭长城到景山公园
    addEdge(&graph, 2, 9, 82, 11, 16, 92, 18, 72, 225);  // 八达岭长城到南锣鼓巷
    addEdge(&graph, 3, 4, 10, 20, 2, 15, 3, 12, 15); // 颐和园到鸟巢
    addEdge(&graph, 3, 5, 8, 16, 2, 12, 3, 10, 12);  // 颐和园到圆明园
    addEdge(&graph, 3, 6, 15, 30, 3, 20, 4, 15, 20);  // 颐和园到北海公园
    addEdge(&graph, 3, 7, 20, 40, 4, 30, 5, 25, 30);  // 颐和园到天坛
    addEdge(&graph, 3, 8, 18, 36, 4, 24, 5, 18, 25);  // 颐和园到景山公园 
    addEdge(&graph, 3, 9, 20, 40, 4, 30, 5, 25, 30); // 颐和园到南锣鼓巷
    addEdge(&graph, 4, 5, 8, 16, 2, 12, 3, 10, 12);   // 鸟巢到圆明园
    addEdge(&graph, 4, 6, 15, 30, 3, 20, 4, 15, 20);  // 鸟巢到北海公园
    addEdge(&graph, 4, 7, 20, 40, 4, 30, 5, 25, 30);  // 鸟巢到天坛
    addEdge(&graph, 4, 8, 18, 36, 4, 24, 5, 18, 25);   // 鸟巢到景山公园
    addEdge(&graph, 4, 9, 18, 36, 4, 24, 5, 18, 25);  // 鸟巢到南锣鼓巷
    addEdge(&graph, 5, 6, 15, 30, 3, 20, 4, 15, 20);   // 圆明园到北海公园
    // 将景点图保存到文件（这里简单保存，按实际可完善格式更规范保存）
    FILE* fp = fopen("graph.txt", "w");
    if (fp == NULL)
    {
        perror("文件打开失败\n");
    }

    fprintf(fp, "%d\n", graph.num_places);
    for (int i = 0; i < graph.num_places; i++) {
        fprintf(fp, "%s %d\n", graph.places[i].name, graph.places[i].ticket_price);
    }
    fprintf(fp, "%d\n", graph.num_edges);
    for (int i = 0; i < graph.num_edges; i++) {
        fprintf(fp, "%d %d %d %d %d %d %d %d %d\n",
            graph.edges[i].src, graph.edges[i].dest, graph.edges[i].distance,
            graph.edges[i].time_bus, graph.edges[i].cost_bus,
            graph.edges[i].time_subway, graph.edges[i].cost_subway,
            graph.edges[i].time_taxi, graph.edges[i].cost_taxi);
    }
    fclose(fp);

    // 从文件读取景点图
    readGraphFromFile(&graph, "graph.txt");

    // 寻找最佳旅游路线，假设从故宫（序号0）开始
    int route[MAX_VERTICES];
    int num_visited;
    int total_time = 0;
    int total_cost = 0;
    findBestRoute(graph, 0, route, &num_visited, &total_time, &total_cost);

    // 输出详细旅游路线信息
    printf("最佳旅游路线（以故宫为起点）：\n");
    for (int i = 0; i < num_visited; i++) {
        printf("%s -> ", graph.places[route[i]].name);
    }
    printf("结束\n");
    printf("总时间：%d 分钟\n", total_time);
    printf("总费用（交通费用 + 门票费用）：%d 元\n", total_cost);

    // 保存旅游路线到文件（这里简单将路线的景点序号输出到文件，你可以按需完善格式）
    saveRouteToFile(route, num_visited, "route.txt");

    return 0;
}
